0739. 每日温度【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 单调栈

1. 📝 题目描述

• leetcode

给定一个整数数组 temperatures，表示每天的温度，返回一个数组 answer，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

---

示例 1：

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2：

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3：

输入: temperatures = [30,60,90]
输出: [1,1,0]

---

提示：

• 1 <= temperatures.length <= 10^5
• 30 <= temperatures[i] <= 100

2. 🎯 s.1 - 单调栈

c

int* dailyTemperatures(int* temperatures, int temperaturesSize, int* returnSize) {
    int* res = (int*)calloc(temperaturesSize, sizeof(int));
    int* stack = (int*)malloc(sizeof(int) * temperaturesSize);
    int top = 0;
    for (int i = 0; i < temperaturesSize; i++) {
        while (top > 0 && temperatures[i] > temperatures[stack[top - 1]]) {
            int j = stack[--top];
            res[j] = i - j;
        }
        stack[top++] = i;
    }
    free(stack);
    *returnSize = temperaturesSize;
    return res;
}

js

/**
 * @param {number[]} temperatures
 * @return {number[]}
 */
var dailyTemperatures = function (temperatures) {
  const n = temperatures.length
  const res = new Array(n).fill(0)
  const stack = []
  for (let i = 0; i < n; i++) {
    while (
      stack.length &&
      temperatures[i] > temperatures[stack[stack.length - 1]]
    ) {
      const j = stack.pop()
      res[j] = i - j
    }
    stack.push(i)
  }
  return res
}

py

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = [0] * n
        stack = []
        for i, t in enumerate(temperatures):
            while stack and t > temperatures[stack[-1]]:
                j = stack.pop()
                res[j] = i - j
            stack.append(i)
        return res

• 时间复杂度：$O(n)$，其中 n 是数组长度
• 空间复杂度：$O(n)$

算法思路：

• 维护单调递减栈，栈中存储索引
• 当前温度大于栈顶对应温度时，栈顶出栈，得到等待天数 i - j